package puzzle.projecteuler.p100;

import java.util.ArrayList;
import java.util.List;

import astudy.util.Combination;
import astudy.util.Permutation;


public class Problem093C {

	/**
	 * 遍历所有可能：不同的数字组合和排列(9!/5!=3024)、运算符号组合(4^3=64)、括号组合(5)
	 * 共计967680种可能
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		int[] c = new int[] {1,2,3,4};
		int M = -1;
		String r = null;
		while (c != null) {
			int m = max(c[0], c[1], c[2], c[3]);
			if (m > M) {
				M = m;
				r = (c[0] + "" + c[1] + "" + c[2] + "" + c[3]);
			}
			c = Combination.next(10, c);
		}

		System.out.println("(abcd) = (" + r + ")");
		System.out.println("count = " + M);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	public static int max(int a, int b, int c, int d) {
		int m = 1;
		while (calc(a,b,c,d,m) != null) {
			m ++;
		}
		return m-1;
	}
	
	/**
	 * 利用a,b,c,d计算r
	 * 如果能够计算，则返回表达式；否则返回null。
	 * @param a
	 * @param b
	 * @param c
	 * @param d
	 * @param r
	 * @return
	 */
	public static String calc(int a, int b, int c, int d, int r) {
		
		int[] tmp = new int[]{a,b,c,d};
		List<int[]> p_nums = getAllPermutation(tmp);
		List<char[]> p_ops = getOperations();
		String[] formulas = getFormulaTemplates();
		for (String formula: formulas) {
			for (int[] nums: p_nums) {
				for (char[] ops: p_ops) {
					double x = calc(formula, nums, ops);
					if (Math.abs(x - r) < 0.00001) {
						String t = formula;
						String[] ts = t.split("n");
						t = ts[0]+nums[0]+ts[1]+nums[1]+ts[2]+nums[2]+ts[3]+nums[3]+((ts.length>4)?ts[4]:"");
						ts = t.split("_");
						t = ts[0]+ops[0]+ts[1]+ops[1]+ts[2]+ops[2]+ts[3];
						return t;
					}
				}
			}
		}
		return null;
	}

	/**
	 * 所有数字的排列 
	 * @param nums
	 * @return
	 */
	private static List<int[]> getAllPermutation(int[] nums) {
		List<int[]> p_nums = new ArrayList<int[]>();
		while (nums != null) {
			int[] tmp = new int[nums.length];
			for (int i = 0; i < nums.length; i ++) tmp[i] = nums[i];
			p_nums.add(tmp);
			nums = Permutation.next(nums);
		}
		return p_nums;
	}
	
	/**
	 * +,-,*,/的所有（可重）排列
	 * @return
	 */
	private static List<char[]> getOperations() {
		List<char[]> p_ops = new ArrayList<char[]>();
		char[] ops = new char[] {'+', '-', '*', '/'};
		for (int i = 0; i < ops.length; i ++) {
			for (int j = 0; j < ops.length; j ++) {
				for (int k = 0; k < ops.length; k ++) {
					p_ops.add(new char[] {ops[i], ops[j], ops[k]});
				}
			}
		}
		return p_ops;
	}
	
	/**
	 * 2:
	 * n_n
	 * 3:
	 * (n_n)_n
	 * n_(n_n)
	 * 4:
	 * n_(n_(n_n))
	 * n_((n_n)_n)
	 * (n_n)_(n_n)
	 * ((n_n)_n)_n
	 * (n_(n_n))_n
	 * @return
	 */
	private static String[] getFormulaTemplates() {
		return new String[] {
				"n_(n_(n_n))", "n_((n_n)_n)", "(n_n)_(n_n)", "((n_n)_n)_n", "(n_(n_n))_n" 
		};
	}
	
	private static double calc(double a, double b, char op) {
		switch (op) {
		case '+':
			return (double)a+b;
		case '-':
			return (double)a-b;
		case '*':
			return (double)a*b;
		case '/':
			return (double)a/(double)b;
		default:
			return 0.0;
		}
	}
	
	private static double calc(String formula, int[] nums, char[] ops) {
		
		if ("n_(n_(n_n))".equalsIgnoreCase(formula)) {
			double r1 = calc(nums[2], nums[3], ops[2]);
			double r2 = calc(nums[1], r1, ops[1]);
			double r3 = calc(nums[0], r2, ops[0]);
			return r3;
		} else if ("n_((n_n)_n)".equalsIgnoreCase(formula)) {
			double r1 = calc(nums[1], nums[2], ops[1]);
			double r2 = calc(r1, nums[3], ops[2]);
			double r3 = calc(nums[0], r2, ops[0]);
			return r3;
		} else if ("(n_n)_(n_n)".equalsIgnoreCase(formula)) {
			double r1 = calc(nums[0], nums[1], ops[0]);
			double r2 = calc(nums[2], nums[3], ops[2]);
			double r3 = calc(r1, r2, ops[1]);
			return r3;
		} else if ("((n_n)_n)_n".equalsIgnoreCase(formula)) {
			double r1 = calc(nums[0], nums[1], ops[0]);
			double r2 = calc(r1, nums[2], ops[1]);
			double r3 = calc(r2, nums[3], ops[2]);
			return r3;
		} else {	//"(n_(n_n))_n"
			double r1 = calc(nums[1], nums[2], ops[1]);
			double r2 = calc(nums[0], r1, ops[0]);
			double r3 = calc(r2, nums[3], ops[2]);
			return r3;
		}
	}
}
